/* Author J. Zobel, April 2001.
   Permission to use this code is freely granted, provided that this
   statement is retained. */

/**
** Modified: Andrew Turpin (aht@cs.rmit.edu.au)
** Date: Thu May  4 11:46:20 EST 2006
**       Fri Mar 16 23:01:56 EST 2007
**
** Modified aturpin@unimelb.edu.au April 2013 for COMP20007 Assignment 2
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "vertex.h"
#include "listops.h"
#include "vector.h"
#include "graph.h"
#include "hashtable.h"

/* Create hash table, allocate space, initialise ptrs to NULL */
HASHREC **
inithashtable() {
    int i;
    HASHREC **ht;

    ht = (HASHREC **) malloc( sizeof(HASHREC *) * TSIZE );

    for(i=0; i<TSIZE; i++)
        ht[i] = (HASHREC *) NULL;

    return(ht);
}


/* Search hash table for given string, return record if found, else NULL */
HASHREC *
hashsearch(HASHREC **ht, char *c) {
//printf("search for >%s<\n",c);
    if (ht == NULL) return NULL;
    HASHREC *htmp, *hprv;
    unsigned int hval = HASHFN(c, TSIZE, SEED);

    for( hprv = NULL, htmp=ht[hval]
        ; htmp != NULL && ccmp(htmp->string, c) != 0
        ; hprv = htmp, htmp = htmp->next )
        ;

    if ( (htmp != NULL) && ( hprv!=NULL )) {    /* move to front on access */
        hprv->next = htmp->next;
        htmp->next = ht[hval];
        ht[hval] = htmp;
    }

    return htmp;
}//hashsearch()

/* 
** Insert string c into ht with vertex label v 
** Does not check for duplicates, so be careful to call hashsearch first.
** SIDE_EFFECT: mallocs space for both entry and s
*/
void
hashinsert(HASHREC **ht, char *s, Label v) {
    if (ht == NULL) return;
    HASHREC *htmp;
    unsigned int hval = HASHFN(s, TSIZE, SEED);

    htmp = (HASHREC *) malloc( sizeof(HASHREC) );
    htmp->string = (char *) malloc( (strlen(s)+1)*sizeof(char) );
    strcpy(htmp->string, s);
    htmp->vertex = v;
    htmp->next = ht[hval];  // put at front of linked list
    ht[hval] = htmp;
}

unsigned int
bitwisehash(char *c, int tsize, unsigned int seed) {
    unsigned int h;

    h = seed;

    int len = strlen(c);
    for(int i = 0 ; i < len ; i++) 
        h ^= ( (h<<5) + c[i] + (h>>2) );
    
    return((unsigned int)((h&0x7fffffff) % tsize));
}//bitwisehash()

// compare numPast, numFuture and list
int
ccmp(char *c1, char *c2) {
    if (c1[0] == c2[0])
        return strcmp(c1, c2);
    else
        return 1;
}

/* print hash table */
void
dumpHashTable(HASHREC **ht) {
    int i;

    for(i=0; i<TSIZE; i++)
        if (ht[i] != NULL) {
            for(HASHREC *htmp=ht[i]; htmp != NULL; ) {
                printf("%s %d\n", htmp->string, htmp->vertex);fflush(stdout);
                htmp = htmp->next;
            }
        }
}// dumpHashTable()
